// note to self sljedeci put ne boriti se s javom u 5 ujutro

package com.lukamikec.kmap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

import android.graphics.RectF;

public class kmap_kgen {
	class čelija {
		public boolean val = false;
		public boolean matched = false;

		public boolean both() {
			return val && !matched;
		}
	};

	class marker {
		public int w = 1;
		public int h = 1;
		public int x = 0;
		public int y = 0;

		public marker(int a, int b, int c, int d) {
			x = a;
			y = b;
			w = c;
			h = d;
		}

		public boolean contains(marker sc) {
			return (sc.x >= x && sc.x + sc.w <= x + w && sc.y >= y && sc.y
					+ sc.h <= y + h);
		}

		public RectF toRectF() {
			return new RectF(x, y, w + x, h + y);
		}
	}

	public class marker_cmp implements Comparator<marker> {

		@Override
		public int compare(marker a, marker b) {

			if (a.w * a.h > b.w * b.h) {
				return -1;
			} else if (a.w * a.h < b.w * b.h) {
				return +1;
			} else {
				return 0;
			}
		}
	}

	public čelija[][] tablica; // č jer mrzim javu

	public ArrayList<marker> markers;

	public ArrayList<String> headers_top;
	public ArrayList<String> headers_left;

	public String var_header_top, var_header_left;

	public String DNO = "";
	
	public int polja_gore;
	public int polja_lijevo;

	boolean Eunmatched() {
		for (int stupac = 0; stupac < polja_gore; ++stupac)
			for (int redak = 0; redak < polja_lijevo; ++redak)
				if (tablica[redak][stupac].both())
					return true;
		return false;
	}

	boolean matches(marker m) {
		// if (m.x + m.w > polja_gore || m.y + m.h > polja_lijevo)
		// return false;
		// e luka nisi mislio na ona kruzenja sto idu okolo naokolo11!

		boolean bar_jedan_sam = false;
		for (int stupac = m.x; stupac < m.x + m.w; ++stupac)
			for (int redak = m.y; redak < m.y + m.h; ++redak) {
				if (!tablica[redak % polja_lijevo][stupac % polja_gore].matched)
					bar_jedan_sam = true;
				if (!tablica[redak % polja_lijevo][stupac % polja_gore].val)
					return false;
			}

		return bar_jedan_sam;
	}

	void match(marker m) {
		for (int stupac = m.x; stupac < m.x + m.w; ++stupac)
			for (int redak = m.y; redak < m.y + m.h; ++redak)
				tablica[redak % polja_lijevo][stupac % polja_gore].matched = true;
		markers.add(m);
	}

	čelija[][] match(marker m, čelija[][] tablica) {
		for (int stupac = m.x; stupac < m.x + m.w; ++stupac)
			for (int redak = m.y; redak < m.y + m.h; ++redak)
				tablica[redak % tablica.length][stupac % tablica[0].length].matched = true;
		return tablica;
		// markers.add(m);
	}

	kmap_kgen(kmap_expr formula) {
		markers = new ArrayList<marker>();

		ArrayList<String> vars = formula.get_vars();
		Collections.sort(vars);

		int vc = vars.size();
		// int polja = (int) Math.pow(2, vc);
		polja_gore = (int) Math.pow(2, (int) ((vc + 1) / 2));
		polja_lijevo = (int) Math.pow(2, (int) (vc / 2));
		headers_top = graycode_gen(polja_gore);
		headers_left = graycode_gen(polja_lijevo);

		int vindx = 0;
		var_header_top = "";
		var_header_left = "";
		for (; vindx < (int) ((vc + 1) / 2); ++vindx)
			var_header_top += vars.get(vindx);
		for (; vindx < (int) ((vc + 1) / 2) + (int) (vc / 2); ++vindx)
			var_header_left += vars.get(vindx);

		tablica = new čelija[polja_lijevo][polja_gore];

		for (int stupac = 0; stupac < polja_gore; ++stupac)
			for (int redak = 0; redak < polja_lijevo; ++redak) {
				String kod = headers_top.get(stupac) + headers_left.get(redak);
				HashMap<String, Boolean> memory = new HashMap<String, Boolean>();

				for (int k = 0; k < kod.length(); ++k)
					memory.put(vars.get(k), kod.substring(k, k + 1).equals("1"));

				čelija č = new čelija(); // fy
				č.val = formula.eval(memory);
				tablica[redak][stupac] = č;
			}

		ArrayList<marker> ms = new ArrayList<marker>();
		for (int x = 1; x <= polja_gore; x *= 2)
			for (int y = 1; y <= polja_lijevo; y *= 2)
				ms.add(new marker(0, 0, x, y));

		Collections.sort(ms, new marker_cmp());

		while (Eunmatched()) {
			for (int k = 0; k < ms.size(); ++k) {
				int szw = ms.get(k).w, szh = ms.get(k).h;

				for (int redak = 0; redak < polja_lijevo; ++redak) {
					for (int stupac = 0; stupac < polja_gore; ++stupac) {
						marker m = new marker(stupac, redak, szw, szh);
						if (matches(m))
							match(m);
					}
				}
			}
		}

		Collections.sort(markers, new marker_cmp());

		boolean kraj = false;

		for (int k = 0; k < markers.size() - 1; ++k) {
			marker trn = markers.get(k);
			čelija[][] tmp = new čelija[polja_lijevo][polja_gore];
			for (int redak = 0; redak < polja_lijevo; ++redak) {
				for (int stupac = 0; stupac < polja_gore; ++stupac) {
					tmp[redak % polja_lijevo][stupac % polja_gore] = new čelija();
					tmp[redak % polja_lijevo][stupac % polja_gore].val = trn
							.contains(new marker(stupac, redak, 1, 1));
				}
			}

			for (int j = 0; j < markers.size(); ++j)
				if (j != k)
					tmp = match(markers.get(j), tmp);

			boolean potrebno = false;
			for (int redak = trn.y; redak < trn.y + trn.h; ++redak)
				for (int stupac = trn.x; stupac < trn.x + trn.w; ++stupac) {
					if (tmp[redak % polja_lijevo][stupac % polja_gore].both())
						potrebno = true;
				}
			if (!potrebno) {
				markers.remove(k);
				--k;
			}

		}

		// zgenerirat DNO:
		for (int k = 0; k < markers.size(); ++k) {
			marker trn = markers.get(k);
			
			for (int v = 0; v < vars.size(); ++v) {
				boolean tr = false, fs = false;
				for (int redak = trn.y; redak < trn.y + trn.h; ++redak)
					for (int stupac = trn.x; stupac < trn.x + trn.w; ++stupac)
					{
						String kod = headers_top.get(stupac) + headers_left.get(redak);
						if (kod.substring(v, v + 1).equals("1"))
							tr = true;
						else
							fs = true;
					}
				if (!(tr && fs) && (tr || fs)) {
					if (fs)
						DNO += "¬";
					DNO += vars.get(v);
				}
			}
			
			if (k + 1 < markers.size())
				DNO += " ∨ ";
		}
		// Collections.reverse(ms);
	}

	public String print() {
		String res = "";
		for (int redak = 0; redak < polja_lijevo; ++redak) {
			for (int stupac = 0; stupac < polja_gore; ++stupac) {
				res += (tablica[redak][stupac].val ? "1" : "0");
			}
			res += "\n";
		}

		return res;
	}

	public ArrayList<String> graycode_gen(int seed) {
		ArrayList<String> res = new ArrayList<String>();
		res.add("0");
		res.add("1");
		while (res.size() < seed) {
			int origs = res.size();
			for (int k = 0; k < origs; ++k) {
				res.add(origs, "1" + res.get(k));
				res.set(k, "0" + res.get(k));
			}
		}
		return res;
	}

}
